/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._107;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Objects;
import java.util.stream.Collectors;

/**
 *
 * 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
 *
 * 例如：
 * 给定二叉树 [3,9,20,null,null,15,7],
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 返回其自底向上的层次遍历为：
 *
 * [
 *   [15,7],
 *   [9,20],
 *   [3]
 * ]
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._107
 * @ClassName: BinaryTreeii
 * @Author: linyaonan
 * @Date: 2019/10/25 15:52
 */
public class BinaryTreeii {

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        // 定义用来存放对应层节点数据的list
        List<List<Integer>> bufferList = new ArrayList<>();
        if (root == null) {
            return bufferList;
        }
        // 层数从0开始
        int index = 0;
        addList(root, index, bufferList);
        // 处理空数据
        bufferList = bufferList.stream().map(this::getNotNullData).collect(Collectors.toList());
        // 翻转数组
        Collections.reverse(bufferList);
        // 处理空数组
        return bufferList.stream().filter(b -> b.size() != 0).collect(Collectors.toList());
    }

    private List<Integer> getNotNullData(List<Integer> orgList) {
        if (orgList == null) {
            return null;
        }
        return orgList.stream().filter(Objects::nonNull).collect(Collectors.toList());
    }

    private void addList(TreeNode node, int index, List<List<Integer>> bufferList) {
        appendData(node, index, bufferList);
        ++index;
        bufferData(index, bufferList, node.left);
        bufferData(index, bufferList, node.right);
    }

    private void bufferData(int index, List<List<Integer>> bufferList, TreeNode left) {
        if (left != null) {
            addList(left, index, bufferList);
        } else {
            appendData(null, index, bufferList);
        }
    }

    private void appendData(TreeNode node, int index, List<List<Integer>> bufferList) {
        if (bufferList.size() - 1 < index) {
            List<Integer> newBuilder = new ArrayList<>();
            newBuilder.add(getNodeVal(node));
            bufferList.add(index, newBuilder);
        } else {
            List<Integer> builder = bufferList.get(index);
            builder.add(getNodeVal(node));
        }
    }

    private Integer getNodeVal(TreeNode node) {
        if (node == null) {
            return null;
        } else {
            return node.val;
        }
    }

}
